Signed networks in social media.
Relations between users on social media sites often reflect a mixture of positive (friendly) and negative (antagonistic) interactions. In contrast to the bulk of research on social networks that has focused almost exclusively on positive interpretations of links between people, we study how the interplay between positive and negative relationships affects the structure of on-line social networks. We connect our analyses to theories of signed networks from social psychology. We find that the classical theory of structural balance tends to capture certain common patterns of interaction, but that it is also at odds with some of the fundamental phenomena we observe — particularly related to the evolving, directed nature of these on-line networks. We then develop an alternate theory of status that better explains the observed edge signs and provides insights into the underlying social mechanisms. Our work provides one of the first large-scale evaluations of theories of signed networks using on-line datasets, as well as providing a perspective for reasoning about social media sites. Author Keywords signed networks, structural balance, status theory, positive
Governance in Social Media A Case Study of the Wikipedia Promotion Process.
Social media sites are often guided by a core group of committed users engaged in various forms of governance. A crucial aspect of this type of governance is deliberation, in which such a group reaches decisions on issues of importance to the site. Despite its crucial — though subtle — role in how a number of prominent social media sites function, there has been relatively little investigation of the deliberative aspects of social media governance. Here we explore this issue, investigating a particular deliberative process that is extensive, public, and recorded: the promotion of Wikipedia admins, which is determined by elections that engage committed members of the Wikipedia community. We find that the group decision-making at the heart of this process exhibits several fundamental forms of relative assessment. First we observe that the chance that a voter will support a candidate is strongly dependent on the relationship between characteristics of the voter and the candidate. Second we investigate how both individual voter decisions and overall election outcomes can be based on models that take into account the sequential, public nature of the voting.
Citing for high impact.

Inferring networks of diffusion and influence.
Information diffusion and virus propagation are fundamental processes talking place in networks. While it is often possible to directly observe when nodes become infected, observing individual transmissions (i.e., who infects whom or who influences whom) is typically very difficult. Furthermore, in many applications, the underlying network over which the diffusions and propagations spread is actually unobserved. We tackle these challenges by developing a method for tracing paths of diffusion and influence through networks and inferring the networks over which contagions propagate. Given the times when nodes adopt pieces of information or become infected, we identify the optimal network that best explains the observed infection times. Since the optimization problem is NP-hard to solve exactly, we develop an efficient approximation algorithm that scales to large datasets and in practice gives provably near-optimal performance. We demonstrate the effectiveness of our approach by tracing information cascades in a set of 170 million blogs and news articles over a one year period to infer how information flows through the online media space. We find that the diffusion network of news tends to have a core-periphery structure with a small set of core media sites that diffuse information to the rest of the Web. These sites tend to have stable circles of influence with more general news media sites acting as connectors between them.


Multiplicative Attribute Graph Model of Real%2DWorld Networks.
Large scale real-world network data, such as social networks, Internet and Web graphs, are ubiquitous. The study of such social and information networks seeks to find patterns and explain their emergence through tractable models. In most networks, especially in social networks, nodes have a rich set of attributes (e.g., age, gender) associated with them. However, many existing network models focus on modeling the network structure while ignoring the features of the nodes. Here we present a model that we refer to as the Multiplicative Attribute Graphs (MAG), which naturally captures the interactions between the network structure and node attributes. We consider a model where each node has a vector of categorical latent attributes associated with it. The probability of an edge between a pair of nodes then depends on the product of individual attribute-attribute similarities. This model yields itself to mathematical analysis and we derive thresholds for the connectivity and the emergence of the giant connected component, and show that the model gives rise to graphs with a constant diameter. We analyze the degree distribution to show that the model can produce networks with either log-normal or power-law degree distribution depending on certain conditions. 1
Empirical comparison of algorithms for network community detection.
Detecting clusters or communities in large real-world graphs such as large social or information networks is a problem of considerable interest. In practice, one typically chooses an objective function that captures the intuition of a network cluster as set of nodes with better internal connectivity than external connectivity, and then one applies approximation algorithms or heuristics to extract sets of nodes that are related to the objective function and that “look like” good communities for the application of interest. In this paper, we explore a range of network community detection methods in order to compare them and to understand their relative performance and the systematic biases in the clusters they identify. We evaluate several common objective functions that are used to formalize the notion of a network community, and we examine several different classes of approximation algorithms that aim to optimize such objective functions. In addition, rather than simply fixing an objective and asking for an approximation to the best cluster of any size, we consider a size-resolved version of the optimization problem. Considering community quality as a function of its size provides a much finer lens with which to examine community detection algorithms, since objective functions and approximation algorithms often have non-obvious size-dependent behavior.
Predicting positive and negative links in online social networks.
We study online social networks in which relationships can be either positive (indicating relations such as friendship) or negative (indicating relations such as opposition or antagonism). Such a mix of positive and negative links arise in a variety of online settings; we study datasets from Epinions, Slashdot and Wikipedia. We find that the signs of links in the underlying social networks can be predicted with high accuracy, using models that generalize across this diverse range of sites. These models provide insight into some of the fundamental principles that drive the formation of signed links in networks, shedding light on theories of balance and status from social psychology; they also suggest social computing applications by which the attitude of one user toward another can be estimated from evidence provided by their relationships with other members of the surrounding social network.
Signed Networks in Social Media
Relations between users on social media sites often reflect a mixture of positive (friendly) and negative (antagonistic) interactions. In contrast to the bulk of research on social networks that has focused almost exclusively on positive interpretations of links between people, we study how the interplay between positive and negative relationships affects the structure of on-line social networks. We connect our analyses to theories of signed networks from social psychology. We find that the classical theory of structural balance tends to capture certain common patterns of interaction, but that it is also at odds with some of the fundamental phenomena we observe — particularly related to the evolving, directed nature of these on-line networks. We then develop an alternate theory of status that better explains the observed edge signs and provides insights into the underlying social mechanisms. Our work provides one of the first large-scale evaluations of theories of signed networks using on-line datasets, as well as providing a perspective for reasoning about social media sites. Author Keywords signed networks, structural balance, status theory, positive
Predicting Positive and Negative Links in Online Social Networks
We study online social networks in which relationships can be either positive (indicating relations such as friendship) or negative (indicating relations such as opposition or antagonism). Such a mix of positive and negative links arise in a variety of online settings; we study datasets from Epinions, Slashdot and Wikipedia. We find that the signs of links in the underlying social networks can be predicted with high accuracy, using models that generalize across this diverse range of sites. These models provide insight into some of the fundamental principles that drive the formation of signed links in networks, shedding light on theories of balance and status from social psychology; they also suggest social computing applications by which the attitude of one user toward another can be estimated from evidence provided by their relationships with other members of the surrounding social network.
Citing for High Impact

Empirical Comparison of Algorithms for Network Community Detection
Detecting clusters or communities in large real-world graphs such as large social or information networks is a problem of considerable interest. In practice, one typically chooses an objective function that captures the intuition of a network cluster as set of nodes with better internal connectivity than external connectivity, and then one applies approximation algorithms or heuristics to extract sets of nodes that are related to the objective function and that “look like” good communities for the application of interest. In this paper, we explore a range of network community detection methods in order to compare them and to understand their relative performance and the systematic biases in the clusters they identify. We evaluate several common objective functions that are used to formalize the notion of a network community, and we examine several different classes of approximation algorithms that aim to optimize such objective functions. In addition, rather than simply fixing an objective and asking for an approximation to the best cluster of any size, we consider a size-resolved version of the optimization problem. Considering community quality as a function of its size provides a much finer lens with which to examine community detection algorithms, since objective functions and approximation algorithms often have non-obvious size-dependent behavior.
Governance in Social Media A case study of the Wikipedia promotion process
Social media sites are often guided by a core group of committed users engaged in various forms of governance. A crucial aspect of this type of governance is deliberation, in which such a group reaches decisions on issues of importance to the site. Despite its crucial — though subtle — role in how a number of prominent social media sites function, there has been relatively little investigation of the deliberative aspects of social media governance. Here we explore this issue, investigating a particular deliberative process that is extensive, public, and recorded: the promotion of Wikipedia admins, which is determined by elections that engage committed members of the Wikipedia community. We find that the group decision-making at the heart of this process exhibits several fundamental forms of relative assessment. First we observe that the chance that a voter will support a candidate is strongly dependent on the relationship between characteristics of the voter and the candidate. Second we investigate how both individual voter decisions and overall election outcomes can be based on models that take into account the sequential, public nature of the voting.
Inferring Networks of Diffusion and Influence
Information diffusion and virus propagation are fundamental processes talking place in networks. While it is often possible to directly observe when nodes become infected, observing individual transmissions (i.e., who infects whom or who influences whom) is typically very difficult. Furthermore, in many applications, the underlying network over which the diffusions and propagations spread is actually unobserved. We tackle these challenges by developing a method for tracing paths of diffusion and influence through networks and inferring the networks over which contagions propagate. Given the times when nodes adopt pieces of information or become infected, we identify the optimal network that best explains the observed infection times. Since the optimization problem is NP-hard to solve exactly, we develop an efficient approximation algorithm that scales to large datasets and in practice gives provably near-optimal performance. We demonstrate the effectiveness of our approach by tracing information cascades in a set of 170 million blogs and news articles over a one year period to infer how information flows through the online media space. We find that the diffusion network of news tends to have a core-periphery structure with a small set of core media sites that diffuse information to the rest of the Web. These sites tend to have stable circles of influence with more general news media sites acting as connectors between them.
Multiplicative Attribute Graph Model of Real%2DWorld Networks
Large scale real-world network data, such as social networks, Internet and Web graphs, are ubiquitous. The study of such social and information networks seeks to find patterns and explain their emergence through tractable models. In most networks, especially in social networks, nodes have a rich set of attributes (e.g., age, gender) associated with them. However, many existing network models focus on modeling the network structure while ignoring the features of the nodes. Here we present a model that we refer to as the Multiplicative Attribute Graphs (MAG), which naturally captures the interactions between the network structure and node attributes. We consider a model where each node has a vector of categorical latent attributes associated with it. The probability of an edge between a pair of nodes then depends on the product of individual attribute-attribute similarities. This model yields itself to mathematical analysis and we derive thresholds for the connectivity and the emergence of the giant connected component, and show that the model gives rise to graphs with a constant diameter. We analyze the degree distribution to show that the model can produce networks with either log-normal or power-law degree distribution depending on certain conditions. 1
On the Convexity of Latent Social Network Inference
In many real-world scenarios, it is nearly impossible to collect explicit social network data. In such cases, whole networks must be inferred from underlying observations. Here, we formulate the problem of inferring latent social networks based on network diffusion or disease propagation data. We consider contagions propagating over the edges of an unobserved social network, where we only observe the times when nodes became infected, but not who infected them. Given such node infection times, we then identify the optimal network that best explains the observed data. We present a maximum likelihood approach based on convex programming with a l1-like penalty term that encourages sparsity. Experiments on real and synthetic data reveal that our method near-perfectly recovers the underlying network structure as well as the parameters of the contagion propagation model. Moreover, our approach scales well as it can infer optimal networks on thousand nodes in a matter of minutes. 1
Supervised Random Walks Predicting and Recommending Links in Social Networks

Kronecker Graphs An Approach to Modeling Networks.

Networks%2C communities and kronecker products.
k (number of nodes in the cluster) Figure 1: An example network and a corresponding Network Community Profile (NCP) plot. Emergence of the web and online computing applications gave rise to rich large scale social activity data. One of the principal challenges then is to build models and understanding of the structure of such large social and information networks. Here I present our work on clustering and community structure in large networks, where clusters are thought of as sets of nodes that are better connected internally than to the rest of the network. We find that large networks have very different clustering structure from well studied small social networks and graphs that are well-embeddable in a low-dimensional structure. In networks of millions of nodes tight clusters exist at only very small size scales up to around 100 nodes, while at large size scales networks becomes expander like. A network model based on Kronecker products efficiently models such core-periphery network structures. The results suggest broader implications for data analysis and machine learning in sparse and noisy high-dimensional social and information networks, where intuitive notions about cluster quality fail.
Tutorial summary Large social and information networks opportunities for ML.

Modeling Blog Dynamics.
How do blogs produce posts? What local, underlying mechanisms lead to the bursty temporal behaviors observed in blog networks? Earlier work analyzed network patterns of blogs and found that blog behavior is bursty and often follows power laws in both topological and temporal characteristics. However, no intuitive and realistic model has yet been introduced, that can lead to such patterns. This is exactly the focus of this work. We propose a generative model that uses simple and intuitive principles for each individual blog, and yet it is able to produce the temporal characteristics of the blogosphere together with global topological network patterns, like power-laws for degree distributions, for inter-posting times, and several more. Our model ZC uses a novel ‘zero-crossing ’ approach based on a random walk, combined with other powerful ideas like exploration and exploitation. This makes it the first model to simultaneously model the topology and temporal dynamics of the blogosphere. We validate our model with experiments on a large collection of 45,000 blogs and 2.2 million posts. 1
Meme%2Dtracking and the dynamics of the news cycle.
Tracking new topics, ideas, and “memes ” across the Web has been an issue of considerable interest. Recent work has developed methods for tracking topic shifts over long time scales, as well as abrupt spikes in the appearance of particular named entities. However, these approaches are less well suited to the identification of content that spreads widely and then fades over time scales on the order of days — the time scale at which we perceive news and events. We develop a framework for tracking short, distinctive phrases that travel relatively intact through on-line text; developing scalable algorithms for clustering textual variants of such phrases, we identify a broad class of memes that exhibit wide spread and rich variation on a daily basis. As our principal domain of study, we show how such a meme-tracking approach can provide a coherent representation of the news cycle — the daily rhythms in the news media that have long been the subject of qualitative interpretation but have never been captured accurately enough to permit actual quantitative analysis. We tracked 1.6 million mainstream media sites and blogs over a period of three months with the total of 90 million articles and we find a set of novel and persistent temporal patterns in the news cycle. In particular, we observe a typical lag of 2.5 hours between the peaks of attention to a phrase in the news media and in blogs respectively, with divergent behavior around the overall peak and a “heartbeat”-like pattern in the handoff between news and blogs. We also develop and analyze a mathematical model for the kinds of temporal variation that the system exhibits.
ShatterPlots Fast Tools for Mining Large Graphs.

Community Structure in Large Networks Natural Cluster Sizes and the Absence of Large Well%2DDefined Clusters.

Monitoring Network Evolution using MDL.
Abstract — Given publication titles and authors, what can we say about the evolution of scientific topics and communities over time? Which communities shrunk, which emerged, and which split, over time? And, when in time were the turning points? We propose TimeFall, which can automatically answer these questions given a social network/graph that evolves over time. The main novelty of the proposed approach is that it needs no user-defined parameters, relying instead on the principle of Minimum Description Length (MDL), to extract the communities, and to find good cut-points in time when communities change abruptly: a cut-point is good, if it leads to shorter data description. We illustrate our algorithm on synthetic and large real datasets, and we show that the results of the TimeFall agree with human intuition. I.
Social networks looking ahead.

Microscopic evolution of social networks.
We present a detailed study of network evolution by analyzing four large online social networks with full temporal information about node and edge arrivals. For the first time at such a large scale, we study individual node arrival and edge creation processes that collectively lead to macroscopic properties of networks. Using a methodology based on the maximum-likelihood principle, we investigate a wide variety of network formation strategies, and show that edge locality plays a critical role in evolution of networks. Our findings supplement earlier network models based on the inherently non-local preferential attachment. Based on our observations, we develop a complete model of network evolution, where nodes arrive at a prespecified rate and select their lifetimes. Each node then independently initiates edges according to a “gap” process, selecting a destination for each edge according to a simple triangle-closing model free of any parameters. We show analytically that the combination of the gap distribution with the node lifetime leads to a power law out-degree distribution that accurately reflects the true network in all four cases. Finally, we give model parameter settings that allow automatic evolution and generation of realistic synthetic networks of arbitrary scale.
Mobile call graphs beyond power%2Dlaw and lognormal distributions.
We analyze a massive social network, gathered from the records of a large mobile phone operator, with more than a million users and tens of millions of calls. We examine the distributions of the number of phone calls per customer; the total talk minutes per customer; and the distinct number of calling partners per customer. We find that these distributions are skewed, and that they significantly deviate from what would be expected by power-law and lognormal distributions. To analyze our observed distributions (of number of calls, distinct call partners, and total talk time), we propose PowerTrack, a method which fits a lesser known but more suitable distribution, namely the Double Pareto LogNormal (DPLN) distribution, to our data and track its parameters over time. Using PowerTrack, we find that our graph changes over time in a way consistent with a generative process that naturally results in the DPLN distributions we observe. Furthermore, we show that this generative process lends itself to a natural and appealing social wealth interpretation in the context of social networks such as ours. We discuss the application of those results to our model and to forecasting.
Statistical properties of community structure in large social and information networks.
A large body of work has been devoted to identifying community structure in networks. A community is often though of as a set of nodes that has more connections between its members than to the remainder of the network. In this paper, we characterize as a function of size the statistical and structural properties of such sets of nodes. We define the network community profile plot, which characterizes the “best ” possible community—according to the conductance measure—over a wide range of size scales, and we study over 70 large sparse real-world networks taken from a wide range of application domains. Our results suggest a significantly more refined picture of community structure in large real-world networks than has been appreciated previously. Our most striking finding is that in nearly every network dataset we examined, we observe tight but almost trivial communities at very small scales, and at larger size scales, the best possible communities gradually “blend in ” with the rest of the network and thus become less “community-like.” This behavior is not explained, even at a qualitative level, by any of the commonly-used network generation models. Moreover, this behavior is exactly the opposite of what one would expect based on experience with and intuition from expander graphs, from graphs that are well-embeddable in a low-dimensional structure, and from small social networks that have served as testbeds of community detection algorithms. We have found, however, that a generative model, in which new edges are added via an iterative “forest fire” burning process, is able to produce graphs exhibiting a network community structure similar to our observations.
Planetary%2Dscale views on a large instant%2Dmessaging network.
We present a study of anonymized data capturing a month of high-level communication activities within the whole of the Microsoft Messenger instant-messaging system. We examine characteristics and patterns that emerge from the collective dynamics of large numbers of people, rather than the actions and characteristics of individuals. The dataset contains summary properties of 30 billion conversations among 240 million people. From the data, we construct a communication graph with 180 million nodes and 1.3 billion undirected edges, creating the largest social network constructed and analyzed to date. We report on multiple aspects of the dataset and synthesized graph. We find that the graph is well-connected and robust to node removal. We investigate on a planetary-scale the oft-cited report that people are separated by “six degrees of separation” and find that the average path length among Messenger users is 6.6. We also find that people tend to communicate more with each other when they have similar age, language, and location, and that cross-gender conversations are both more frequent and of longer duration than conversations with the same gender.
Epidemic thresholds in real networks.
How will a virus propagate in a real network? How long does it take to disinfect a network given particular values of infection rate and virus death rate? What is the single best node to immunize? Answering these questions is essential for devising network-wide strategies to counter viruses. In addition, viral propagation is very similar in principle to the spread of rumors, information, and “fads, ” implying that the solutions for viral propagation would also offer insights into these other problem settings. We answer these questions by developing a nonlinear dynamical system (NLDS) that accurately models viral propagation in any arbitrary network, including real and synthesized network graphs. We propose a general epidemic threshold condition for the NLDS system: we prove that the epidemic threshold for a network is exactly the inverse of the largest eigenvalue of its adjacency matrix. Finally, we show that below the epidemic threshold, infections die out at an exponential rate. Our epidemic threshold model subsumes many known thresholds for special-case graphs (e.g., Erdös–Rényi, BA powerlaw, homogeneous). We demonstrate the predictive power of our model with extensive experiments on real and synthesized graphs, and show that our threshold condition holds for arbitrary graphs. Finally, we show how to utilize our threshold condition for practical uses: It can dictate which nodes to immunize; it can assess the effects of a throttling
Community Structure in Large Networks Natural Cluster Sizes and the Absence of Large Well%2DDefined Clusters

Scalable modeling of real graphs using Kronecker multiplication.
Given a large, real graph, how can we generate a synthetic graph that matches its properties, i.e., it has similar degree distribution, similar (small) diameter, similar spectrum, etc? We propose to use “Kronecker graphs”, which naturally obey all of the above properties, and we present KronFit, a fast and scalable algorithm for fitting the Kronecker graph generation model to real networks. A naive approach to fitting would take super-exponential time. In contrast, Kron-Fit takes linear time, by exploiting the structure of Kronecker product and by using sampling. Experiments on large real and synthetic graphs show that KronFit indeed mimics very well the patterns found in the target graphs. Once fitted, the model parameters and the resulting synthetic graphs can be used for anonymization, extrapolations, and graph summarization. 1.
Information Survival Threshold in Sensor and P2P Networks.
Abstract—Consider a network of, say, sensors, or P2P nodes, or bluetooth-enabled cell-phones, where nodes transmit information to each other and where links and nodes can go up or down. Consider also a ‘datum’, that is, a piece of information, like a report of an emergency condition in a sensor network, a national traditional song, or a mobile phone virus. How often should nodes transmit the datum to each other, so that the datum can survive (or, in the virus case, under what conditions will the virus die out)? Clearly, the link and node fault probabilities are important — what else is needed to ascertain the survivability of the datum? We propose and solve the problem using non-linear dynamical systems and fixed point stability theorems. We provide a closedform formula that, surprisingly, depends on only one additional parameter, the largest eigenvalue of the connectivity matrix. We illustrate the accuracy of our analysis on realistic and real settings, like mote sensor networks from Intel and MIT, as well as Gnutella and P2P networks. I.
Cost%2Deffective outbreak detection in networks.
� One of the networks is a spread of a disease, the other one is product recommendations � Which is which?  ☺ Diffusion in Social Networks � A fundamental process in social networks: Behaviors that cascade from node to node like an epidemic – News, opinions, rumors, fads, urban legends, … – Word‐of‐mouth effects in marketing: rise of new websites, free web based services – Virus, disease propagation – Change in social priorities: smoking, recycling – Saturation news coverage: topic diffusion among bloggers – Internet‐energized political campaigns – Cascading failures in financial markets – Localized effects: riots, people walking out of a lectureEmpirical Studies of Diffusion � Experimental studies of diffusion have long history: – Spread of new agricultural practices [Ryan‐Gross 1943] • Adoption of a new hybrid‐corn between the 259 farmers in Iowa • Classical study of diffusion • Interpersonal network plays important role in adoption � Diffusion is a social process – Spread of new medical practices [Coleman et al 1966] • Studied the adoption of a new drug between doctors in Illinois • Clinical studies and scientific evaluations were not sufficient to convince the doctors • It was the social power of peers that led to adoptionDiffusion in Networks � Initially some nodes are active � Active nodes spread their influence on the other nodes, and so on … a d
Web projections learning from contextual subgraphs of the web.
Graphical relationships among web pages have been leveraged as sources of information in methods for ranking search results. To date, specific graphical properties have been used in these analyses. We introduce web projections, a methodology that generalizes prior efforts on exploiting graphical relationships of the web in several ways. With the approach, we create subgraphs by projecting sets of pages and domains onto the larger web graph, and then use machine learning to construct predictive models that consider graphical properties as evidence. We describe the method and present experiments that illustrate the construction of predictive models of search result quality and user query reformulation.
Patterns of Cascading Behavior in Large Blog Graphs.
How do blogs cite and influence each other? How do such links evolve? Does the popularity of old blog posts drop exponentially with time? These are some of the questions that we address in this work. Blogs (weblogs) have become an important medium of information because of their timely publication, ease of use, and wide availability. In fact, they often make headlines, by discussing and discovering evidence about political events and facts. Often blogs link to one another, creating a publicly available record of how information and influence spreads through an underlying social network. Aggregating links from several blog posts creates a directed graph which we analyze to discover the patterns of information propagation in blogspace, and thereby understand the underlying social network. Here we report some surprising findings of the blog linking and information propagation structure, after we analyzed one of the largest available datasets, with 45, 000 blogs and ≈ 2.2 million blog-postings. Our analysis also sheds light on how rumors, viruses, and ideas propagate over social and computer networks.
Web projections learning from contextual subgraphs of the web.
Graphical relationships among web pages have been leveraged as sources of information in methods for ranking search results. To date, specific graphical properties have been used in these analyses. We introduce web projections, a methodology that generalizes prior efforts on exploiting graphical relationships of the web in several ways. With the approach, we create subgraphs by projecting sets of pages and domains onto the larger web graph, and then use machine learning to construct predictive models that consider graphical properties as evidence. We describe the method and present experiments that illustrate the construction of predictive models of search result quality and user query reformulation.
The dynamics of viral marketing.
We present an analysis of a person-to-person recommendation network, consisting of 4 million people who made 16 million recommendations on half a million products. We observed the propagation of recommendations and the cascade sizes, which can be explained by a stochastic model. We then established how the recommendation network grows over time and how e#ective it is from the viewpoint of the sender and receiver of the recommendations. While on average recommendations are not very e#ective at inducing purchases and do not spread very far, there are product and pricing categories for which viral marketing seems to be very e#ective.
The dynamics of viral marketing.
We present an analysis of a person-to-person recommendation network, consisting of 4 million people who made 16 million recommendations on half a million products. We observed the propagation of recommendations and the cascade sizes, which can be explained by a stochastic model. We then established how the recommendation network grows over time and how e#ective it is from the viewpoint of the sender and receiver of the recommendations. While on average recommendations are not very e#ective at inducing purchases and do not spread very far, there are product and pricing categories for which viral marketing seems to be very e#ective.
Data association for topic intensity tracking.
We present a unified model of what was traditionally  viewed as two separate tasks: data association  and intensity tracking of multiple topics  over time. In the data association part, the task  is to assign a topic (a class) to each data point,  and the intensity tracking part models the bursts  and changes in intensities of topics over time.
Sampling from large graphs.
Given a huge real graph, how can we derive a representative sample? There are many known algorithms to compute interesting measures (shortest paths, centrality, betweenness, etc.), but several of them become impractical for large graphs. Thus graph sampling is essential.
Patterns of Influence in a Recommendation Network.
Information cascades are phenomena in which individuals  adopt a new action or idea due to influence by others. As such a process  spreads through an underlying social network, it can result in widespread  adoption overall. We consider information cascades in the context  of recommendations, and in particular study the patterns of cascading  recommendations that arise in large social networks. We investigate a  large person-to-person recommendation network, consisting of four million  people who made sixteen million recommendations on half a million  products. Such a dataset allows us to pose a number of fundamental  questions: What kinds of cascades arise frequently in real life? What features  distinguish them? We enumerate and count cascade subgraphs on  large directed graphs; as one component of this, we develop a novel efficient  heuristic based on graph isomorphism testing that scales to large  datasets. We discover novel patterns: the distribution of cascade sizes is  approximately heavy-tailed; cascades tend to be shallow, but occasional  large bursts of propagation can occur. The relative abundance of di#erent  cascade subgraphs suggests subtle properties of the underlying social  network and recommendation process.
GMine A System for Scalable%2C Interactive Graph Visualization and Mining.
Several graph visualization tools exist. However, they are not able to handle large graphs, and/or they do not allow interaction. We are interested on large graphs, with hundreds of thousands of nodes. Such graphs bring two challenges: the first one is that any straightforward interactive manipulation will be prohibitively slow. The second one is sensory overload: even if we could plot and replot the graph quickly, the user would be overwhelmed with the vast volume of information because the screen would be too cluttered as nodes and edges overlap each other. Our GMine system addresses both these issues, by using summarization and multi-resolution. GMine offers multi-resolution graph exploration by partitioning a given graph into a hierarchy of communities-within-communities and storing it into a novel R-tree-like structure which we name G-Tree. GMine offers summarization by implementing an innovative subgraph extraction algorithm and then visualizing its output. 1.
Impact of Linguistic Analysis on the Semantic Graph Coverage and Learning of Document Extracts.
Automatic document summarization is a problem of creating a document surrogate that adequately represents the full document content. We aim at a summarization system that can replicate the quality of summaries created by humans. In this paper we investigate the machine learning method for extracting full sentences from documents based on the document semantic graph structure. In particular, we explore how the Support Vector Machines (SVM) learning method is affected by the quality of linguistic analyses and the corresponding semantic graph representations. We apply two types of linguistic analysis: (1) a simple part-of-speech tagging of noun phrases and verbs and (2) full logical form analysis which identifies Subject-Predicate-Object triples, and then build the semantic graphs. We train the SVM classifier to identify summary nodes and use these nodes to extract sentences. Experiments with the DUC 2002 and CAST datasets show that the SVM based extraction of sentences does not differ significantly for the simple and the sophisticated syntactic analysis. In both cases the graph attributes used in learning are essential for the classifier performance and the quality of extracted summaries.
Graphs over time densification laws
How do real graphs evolve over time? What are &#034;normal&#034; growth patterns in social, technological, and information networks? Many studies have discovered patterns in static graphs, identifying properties in a single snapshot of a large network, or in a very small number of snapshots; these include heavy tails for in- and out-degree distributions, communities, small-world phenomena, and others. However, given the lack of information about network evolution over long periods, it has been hard to convert these findings into statements about trends over time. Here we study
Realistic
A vast body of theoretical research has focused either on overly simplistic models of parallel  computation, notably the PRAM, or overly specific models that have few representatives in  the real world. Both kinds of models encourage exploitation of formal loopholes, rather than  rewarding development of techniques that yield performance across a range of current and  future parallel machines. This paper offers a new parallel machine model, called LogP, that  reflects the critical technology trends underlying parallel computers. It is intended to serve  as a basis for developing fast, portable parallel algorithms and to offer guidelines to machine  designers. Such a model must strike a balance between detail and simplicity in order to reveal  important bottlenecks without making analysis of interesting problems intractable. The model  is based on four parameters that specify abstractly the computing bandwidth, the communication  bandwidth, the communication delay, and the efficiency of coupling communication  and computation. Portable parallel algorithms typically adapt to the machine configuration, in  terms of these parameters. The utility of the model is demonstrated through examples that are  implemented on the CM-5.
The Dynamics of Viral Marketing
We present an analysis of a person-to-person recommendation network, consisting of 4 million people who made 16 million recommendations on half a million products. We observed the propagation of recommendations and the cascade sizes, which can be explained by a stochastic model. We then established how the recommendation network grows over time and how e#ective it is from the viewpoint of the sender and receiver of the recommendations. While on average recommendations are not very e#ective at inducing purchases and do not spread very far, there are product and pricing categories for which viral marketing seems to be very e#ective.
Modeling Link Qualities in a Sensor Network.
Sensor networks are ad-hoc wireless networks of small, low-cost sensors, which can measure characteristics of their environment. Autonomous low-cost sensors often have limited battery life, and are prone to failures and communication losses. It is thus important to devise efficient power usage, communication and message routing schemes. In this work, we concentrate on estimating the link qualities between pairs of sensors in a natural environment. The estimation is a basic component of algorithms that optimize the power of radio transmission signal, communication schedules, and a routing scheme. Our results show that simple regression models give estimates with only 6 % error. We also show the dimensionality reduction techniques help us understand the topology of the communication network and identify potential bottlenecks in the network. Povzetek: Z uporabo metod za zmanjšanje dimenzije podatkov in nelinearnih modelov v omrežju senzorjev je možno doseči zmanjšanje napake za 6%. 1
The Download Estimation task on KDD Cup 2003.
This paper describes our work on the Download Estimation task for KDD Cup 2003. The task requires us to estimate how many times certain papers have been downloaded in the first 60 days after they have been published on arXiv.org, a preprint server for papers on physics and related areas. The training data consists of approx. 29000 papers (both full text and some metadata were available), the graph of citations among those papers, and information about the downloads of a subset of these papers (not only the number of downloads, but timestamps of individual downloads as well). Our approach is based on an extension of the bag-of-words model, with linear SVM regression as the learning algorithm. We describe our experiments with various kinds of features, both helpful and useless ones. We focus particularly on issues of feature weighting, which turns out to be quite important for this task.
Linear Programming Boosting for Uneven Datasets.
The paper extends the notion of linear  programming boosting to handle uneven  datasets. Extensive experiments with text  classification problem compare the performance  of a number of di#erent boosting  strategies, concentrating on the problems  posed by uneven datasets.
The Download Estimation task on KDD Cup 2003.
This paper describes our work on the Download Estimation task for KDD Cup 2003. The task requires us to estimate how many times certain papers have been downloaded in the first 60 days after they have been published on arXiv.org, a preprint server for papers on physics and related areas. The training data consists of approx. 29000 papers (both full text and some metadata were available), the graph of citations among those papers, and information about the downloads of a subset of these papers (not only the number of downloads, but timestamps of individual downloads as well). Our approach is based on an extension of the bag-of-words model, with linear SVM regression as the learning algorithm. We describe our experiments with various kinds of features, both helpful and useless ones. We focus particularly on issues of feature weighting, which turns out to be quite important for this task.
